package code;

import java.util.ArrayList;
import java.util.List;

public class Code57 {
	static public class Interval {
		int start;
		int end;
		Interval() { 
			start = 0; 
			end = 0; 
		}
		Interval(int s, int e) { 
			start = s; 
			end = e; 
			}
	}
	
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result=new ArrayList<Interval>();
        int i,j;
        int n=intervals.size();
        if(n==0){
        	result.add(newInterval);
        	return result;
        }
        int startIdx=-1;
        int endIdx=-1;
        for(i=0;i<n;i++){
        	if(intervals.get(i).start<=newInterval.start && 
        			intervals.get(i).end>=newInterval.start){
        		startIdx=i;
        		break;
        	}
        }
        for(i=0;i<n;i++){
        	if(intervals.get(i).start<=newInterval.end && 
        			intervals.get(i).end>=newInterval.end){
        		endIdx=i;
        		break;
        	}
        }
        if(startIdx!=-1 && startIdx==endIdx){
        	//在同一区间内
        	return intervals;
        }
        //插入的新区间没有交叉，不需要合并，直接找到插入的位置，插入区间即可
        if(startIdx==-1 && endIdx==-1){
        	
        	//插在最左边
        	if(intervals.get(0).start>newInterval.end){
        		intervals.add(0, newInterval);
        		return intervals;
        	}
        	else if(intervals.get(intervals.size()-1).end<newInterval.start){
        		intervals.add(newInterval);
        		return intervals;
        	}
        	//新区间完全覆盖所有的区间
        	else if(intervals.get(n-1).end<newInterval.end && 
        				intervals.get(0).start>newInterval.start){
        		result.add(newInterval);
        		return result;
        	}
        	else {
        		//插在中间
            	for(i=0;i<n-1;i++){
            		if(intervals.get(i).end<newInterval.start &&
            				intervals.get(i+1).start>newInterval.start){
            			break;
            		}
            	}
            	//判断是否会完全的覆盖地i+1段
            	if(newInterval.start<intervals.get(i+1).start &&
            			newInterval.end>intervals.get(i+1).end){
            		intervals.get(i+1).start=newInterval.start;
            		intervals.get(i+1).end=newInterval.end;
            	}
            	else	
            		intervals.add(i+1,newInterval);
            	return intervals;
        	}
        }
        //新插入的区间，左边结点有交叉，需要合并.需要找到新段右边插入的位置
        else if(startIdx!=-1  && endIdx==-1){
        	//所以右边端点不可能在最左边
        	if(intervals.get(intervals.size()-1).end<newInterval.end){
        		//合并
        		intervals.get(startIdx).end=newInterval.end;
        		for(i=0;i<=startIdx;i++){
        			result.add(intervals.get(i));
        		}
        		return result;
        	}
        	else{//找到插入的位置
        		for(i=startIdx;i<n;i++){
        			if(intervals.get(i).end<newInterval.end && 
        					intervals.get(i+1).start>newInterval.end){
        				break;
        			}
        		}
        		//合并
        		intervals.get(startIdx).end=newInterval.end;
        		for(j=0;j<=startIdx;j++){
        			result.add(intervals.get(j));
        		}
        		//中间的合并了
        		for(j=i+1;j<n;j++){
        			result.add(intervals.get(j));
        		}
        		return result;
        	}
        }
        //新段的左边没有交叉,但是右边有交叉
        else if(startIdx==-1 && endIdx!=-1){
        	//左边不可能在最右边
        	if(newInterval.start<intervals.get(0).start){
        		//在左边,合并
        		intervals.get(endIdx).start=newInterval.start;
        		for(i=endIdx;i<n;i++){
        			result.add(intervals.get(i));
        		}
        		return result;
        	}
        	else{
        		for(i=0;i<endIdx;i++){
        			if(intervals.get(i).end<newInterval.start && 
        					intervals.get(i+1).start>newInterval.start){
        				break;
        			}
        		}
//        		intervals.get(i+1).start=newInterval.start;
//        		intervals.get(i+1).end=newInterval.end;
        		newInterval.end=intervals.get(endIdx).end;
        		for(j=0;j<=i;j++){
        			result.add(intervals.get(j));
        		}
        		result.add(newInterval);
        		
        		for(i=endIdx+1;i<n;i++){
        			result.add(intervals.get(i));
        		}
        		return result;
        	}
        }
        else{//新段两段都落在区间内
        	intervals.get(startIdx).end=intervals.get(endIdx).end;
        	for(i=0;i<=startIdx;i++){
        		result.add(intervals.get(i));
        	}
        	
        	for(i=endIdx+1;i<n;i++){
        		result.add(intervals.get(i));
        	}
        	return result;
        }
    }
    public static void main(String[] args){
    	Code57 code=new Code57();
    	List<Interval> intervals=new ArrayList<Interval>();
//    	Interval[2] intervals=new Interval[2];
    	intervals.add(new Interval(2,7));
    	intervals.add(new Interval(8,8));
    	intervals.add(new Interval(10,10));
    	intervals.add(new Interval(12,13));
    	intervals.add(new Interval(16,19));
    	Interval newInterval=new Interval(9,17);
    	
    	List<Interval> ans=code.insert(intervals, newInterval);
    	for(int i=0;i<ans.size();i++){
    		System.out.println(ans.get(i).start+"--> "+ans.get(i).end);
    	}
    }
}
